A Content Addressable Memory (“CAM”) includes a plurality of CAM cells arranged in rows and columns. As is well-known in the art, a CAM cell can be dynamic memory based or static memory based and can be a binary cell or a ternary cell. A binary CAM cell has two possible logic states ‘1’ and ‘0’. A ternary CAM cell has three possible logic states ‘0’, ‘1’ and don't care (‘X’) encoded in two bits.
A CAM entry can include a plurality of CAM cells. For example, a 72-ternary bit entry includes 72 ternary CAM cells. A search and compare feature allows all of the CAM cells in the CAM to be searched for an entry storing data that matches a search key. If an entry matching the search key is stored in the CAM, outputs typically provide the address of the matching entry, that is, the match address, a match flag indicating whether there is a match and a multiple match flag indicating whether there is more than one match. The match address may be used to find data associated with the search key stored in a separate memory in a location specified by the match address.
Each entry in the CAM has an associated match line coupled to each CAM cell in the entry. Upon completion of the search, the state of the match line for the entry indicates whether the entry matches the search key. The match lines from all entries in the CAM are provided to a match line detection circuit to determine if there is a matching entry for the search key in the CAM and then the result of the match line detection circuit is provided to a priority encoder. If there are multiple match entries for the search key in the CAM, the priority encoder selects the match entry with the highest, priority. The priority encoder also provides the match address and a match flag. The match flag is enabled when there is at least one match/hit.
Each entry in the CAM is searched for a match for the search key. Typically high density CAMs are configured for 72-bit, 144-bit or 288-bit width entries. For example, the Mosaid CLASS-IC DC9288 is a 9 M bit DRAM-based CAM configurable as 128K 72-bit entries, 64K 144-bit entries or 32K 288-bit entries. The size of the priority encoder is proportional to the number of entries. Thus, in order to decrease the cost of the CAM, the width of each entry is increased to decrease the total number of entries.
CAMs have many applications including address lookups. For example, a CAM can be used to select a next hop address corresponding to an Internet Protocol (IP) destination addresses. There are two versions of the Internet Protocol. Internet Protocol Version 4 (IPv4) uses a 32-bit destination address and Internet Protocol Version 6 (IPv6) uses a 128-bit destination address. With a 32-bit destination address, there are 232 (4G) possible destination addresses and with a 128-bit destination address there are 2128 possible IPv6 destination addresses. While IP addresses are typically multiples of 32 bits, CAM entries are typically multiples of 36 bits. The extra bits in CAM entries permit user specific data to be stored along with the IP address.
For example, a 32-bit IPv4 destination addresses can be stored in a CAM configured with 128K 72-bit entries with one 32-bit IPv4 destination address stored in each 72-bit CAM entry. By storing one 32-bit IPv4 destination address per CAM entry, a matching entry for a search key can be found in a single search of all entries in the CAM. However, this is an inefficient use of memory because less than 50% of the memory is used, with only 32-bits of each 72-bit entry storing valid data.
Memory efficiency can be increased by storing two 32-bit IPv4 destination addresses per entry in the CAM. For example, bits 35:0 of the 72-bit CAM entry can be assigned for storing one of the 32-bit IPv4 destination addresses and bits 71:36 can be assigned for storing the other. A masked command is issued to restrict the search for a match to the appropriate bits in each CAM entry. With two destination addresses per CAM entry, two separate masked search commands must be issued to find a match for a search key stored in the CAM. For example, a first masked search command is issued to search for a match in the bits 35:0 of all of the 72-bit CAM entries with all other bits in the entries masked. A second masked search command is issued to search for a match in bits 71:36 of the 72-bit CAM entries with all other bits masked. Although memory use is efficient, search time is increased because of the multiple searches.